package Graph;

import java.util.List;

public class bellmanFord_dp {
    //bellmanFord 动态规划版本
    public static void main(String[] args) {
        List<Edge> edges = List.of(
                new Edge(6, 5, 9),
                new Edge(4, 5, 6),
                new Edge(1, 6, 14),
                new Edge(3, 6, 2),
                new Edge(3, 4, 11),
                new Edge(2, 4, 15),
                new Edge(1, 3, 9),
                new Edge(1, 2, 7)
        );
        int[] dp = new int[7];
        dp[1] = 0;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        print(dp);
        for (int i = 0; i < 5; i++) {
            edges.forEach(e -> {
                if (dp[e.from] != Integer.MAX_VALUE) {
                    //新                     旧           所有的from
                    dp[e.to] = Integer.min(dp[e.to], dp[e.from] + e.weigth);
                }
            });
        }
        print(dp);

    }

    public static void print(int[] dist) {
        System.out.println("-----");
        for (int ints : dist) {
            System.out.print(ints != Integer.MAX_VALUE ? ints + " " : "∞" + " ");
        }
        System.out.println();

    }
}
